Deterministic Finite Automata

有限元自动机是一个对于有限内存的机器的很好的模拟

状态机如何工作

很多东西都是可以用状态机去表示的, 如一个开灯的开关, 如果在关灯状态, 则按开灯灯就打开, 按关灯按钮, 状态不变. 如果在开灯状态, 按关灯按钮会转跳到关灯状态, 按开灯按钮状态不变.

开灯

关灯

状态机通常会有一个特殊的状态是Accept状态, 如果最终指令执行完, 停在了这个状态, 则最终输出Accept, 否则输出reject.
并且, 状态机是可以被语言表示的, 比如我们可以设计出一种状态机, 它只会接受以下这种语言
我们就可以说M recognizes 这个语言.
每种状态机只会认识一种语言, 我们记作L(M) 如果这个状态机不接受任何字符串, 则这个L(M)是个空集.

我们可以把这个L(M)完全当作一个Language, 所以可以说

反过来, 如果一个语言可以被状态机所recognized, 则这个语言可以说是regular language
如:
是一种regular language, 而

不是个regular language, 之后会证明它为什么不是

需要注意的是, 每个状态机只会识别一个Language, 如果一个状态机识别集合A, 但有个集合B, 它是A的子集, 我们仍然不能说状态机识别B, 只能说它接受B. 因为如果需要识别, 则这个集合需要包含这个机器M所接受的所有字符串

限制与能力

对于有限元自动机, 他的功能就是去解决关于regular language的问题, 但限制就是无法解决关于不是regular language的问题.

表达一个DFA

k-tuple - a sequence of k elements, k≥1
对于一个有限元自动机M, 它有五个元组:

符号 意思
a finite set of states, 有限的状态, 这里有三个
a finites set of symbols, called the alphabet, 这个自动机接受的符号
transition function, 转移方程
the start state, 只能有一个起始点, 这里是q1作为起始点
set of accept states, 能有多个结束的点

有限状态机.png

如果一个状态机的F是空集, 那么它是没有终点, 也就是说它不会接受任何字符串, 所以它识别的语言也是空集

设计一个状态机

设计状态机的过程就像算法一样, 没有固定的公式, 更多的是靠自己的感觉

比如
这个状态机就可以有两个状态, 然后互相用1转跳, 如果转跳奇数次, 都会转跳到目标, 而转跳到偶数次, 都会转跳回原位.
Pasted image 20250108140021.png

这个问题可以认为, 只要出现连续的001, 就可以直接结束了, 所以, 我们需要只要是1, 就回到原点, 而连续的两个0就会进入一个状态: 它只会管有没有1出现, 因为不管后面出现多少个0, 都没有违反规则, 而只要出现了1, 就满足要求了.
Pasted image 20250108140133.png

需要注意的是, 虽然上面说过如何让语言变成空集, 但我们仍然需要让状态机加上状态转移方程(也就是箭头), 不然这个状态机就没有任何alphabet. 除非题目明确规定alphabet也是空, 并且, alphabet里有的元素, 必须在每个状态机上都有箭头来应对新出现的字符

如果一个状态机添加了一个新的元素在alphabet中, 如果他的language没有改变, 则可以说这个状态机也没有改变, 就像在一个算法中添加了一条注释一样, 这个算法没有受到影响, 那么它就是本来的算法.

Regular Operation

这是一种对于language的操作:

Union:
Concatenation:

Star:
并且, 空字符串也会在这个合集里面, 因为k可以是0

前面两个都比较好理解, 最后一个就是把A合集里任意多的元素以任意顺序和任意数量组合而成.
比如{0011},{},{0100111}都是{0,1}^*

并且, Concatenation也是有点注意的地方的: 如果合集B是个空集, 则A◦B也会是空集, 因为无法从B中选择任何元素, 所以也组成不了任何东西

Closure properties

这种操作也遵循闭包性质, 就像int+int永远会等于int的一样, 但int / int不一定会得到int一样

  • 如果两个language是regular language, 则这两个语言的union, 也会是regular language
  • 如果两个language是regular language, 则这两个语言的Concatenation, 也会是regular language
  • 如果某个language是regular language, 则这个语言的Star, 也会是regular language

Proof:

Union
假设存在M1,M2两个机器, 分别认识两个语言A,B, 我们需要证明, 存在一个机器, 它认识A U B, 换句话说, 给一个String, 这个新机器M只有在M1或M2接受它的时候才会接受.

其实, 想找到这个新机器M, 是蛮容易的: 可以把M1和M2里所有的节点都组合起来, 成为一个一个的节点对. 然后把M1和M2所有的转移方程搬到M机器里面, 就可以得到一个新机器, 只接受M1或M2的String
Pasted image 20250113135003.png

因为在Finite Automata Theory > NFA -> DFA中说过, 因为NFA可以转换成DFA, 所以用NFA证明会更加简单. 有了NFA, 我们就不用把所有的可能性组合起来了, 我们可以有并行这个操作了: 也就是写一个起始点, 这个起始点用ε转移方程同时连接M1和M2的起始点. 所以根据NFA的特性, 他会同时走两条路, 只要有一条到accept state, 就可以说这个NFA认识这个语言.

Intersection

注意, 这个不是Concatenation
这个只要理解Union后就很好理解, 只要Accept State变成两个Machine里都有的Final State就行

Concatenation
我们的目标是给一个M1和M2, 能找到一个新机器, 这个机器只能接受M1和M2中分别选一个String连接到一起产生的新String.

想做出这样的机器, 我们可以让M1的Accept State连接到M2的Start State. 也就是说只要前半段一旦被接受, 那么立刻转跳到M2的Start State.
这样看起来是正确的, 但实际上这个方法无法知道哪段是M1的, 哪段是M2的, 可能我们太早转跳到M2, 导致多出来的那段字符让M2不接受.

所以我们需要一个新的工具来解决这种事情 - NFA

有了NFA, 我们在M1的accept state的时候, 可以用NFA的特性 - 做个分支, 一条去M2起点, 一条继续走走M1的正常变换. 最后, 只要有一个分支到accept state, 就算这个M接受, 并且这个string同时被M1和M2接受.

Star
这个听起来更加复杂一些:
也就是说M中任意多个string串起来, 得到的string都需要被这个新M识别.
其实, 我们可以认为这是一个Concatenation的问题: 也就是每次到accept state后, 都会有个分支: 一个是继续M原本的分支, 另外一个是ε转移方程, 这个方程会返回到起点.
通过NFA, 我们就可以自动把这个一大长串的string 拆成一个个的被原本的M所识别的string.
需要注意的是, 由于k可以等于0, 所以对于空字符串也需要被识别, 所以起点也需要变成accept state.

Nondeterministic Finite Automata

Pasted image 20250113140920.png
上面学的状态机是DFA跟这里的NFA的区别是:

  • NFA不必需要对一个状态设计所有的状态
  • NFA有ε-transition, 也就是说它可以不读取任何字符, 直接过去
  • NFA有多种路径, 比如上面的q1可以有两条路走, 只要有一条路到Accept State就算接受
    q1q10q1q2q31q1q30no where to goq1q21q3q4q4q1q2q31q4

表达一个NFA

对于一个NFA, 它有五个元组:

符号 意思
a finite set of states, 有限的状态
a finites set of symbols, called the alphabet, 这个自动机接受的符号
跟DFA的区别是, 它里面还包含了ε
transition function, 转移方程, 和DFA的区别就是由于ε的存在, 虽然从一个状态只能转移到另一个状态, 但ε可以让转移有更多的结果
the start state, 只能有一个起始点, 这里是q1作为起始点
set of accept states, 能有多个结束的点

由于NFA的节点转移时不会包含所有的字符, 所以在画表格来表示的时候, 需要在没有转移的时候写一个空集符号来表示这个字符在这个节点不会转移(或者说在这读到这个字符就会结束)

设计一个NFA

比如我们想设计一个NFA, 它只接受一个string, 它的倒数第三个字符是1:

q1q2q3q10,110,10,1

NFA -> DFA

每一个NFA, 都是可以变成DFA的. 也就是, 永远存在一种DFA, 它会识别和NFA同样的语言.
推论: 如果一个语言想要是regular language, 则它一定又一个识别它的NFA, 至于为什么不用DFA了, 是因为NFA通常比DFA更加简洁

证明

假设: 如果有一个NFA - M认识语言A, 则存在一个DFA - M'认识A

证明: 首先假设M没有ε转移, 对于有ε转移的情况之后会讨论. 而剩下的NFA的特性就是: 一个节点不用有所有字符的转移方程, 一个节点可能有两个或以上的状态方程.
对于没有字符的转移方程, 可以设计一个dummy state, 让状态进去就永远出不来了
对于两个或以上的状态方程, 可以把所有的subset给写出来, 然后让这个subset包含了所有可能去的地方:
q1q2q3011q1q2q1q301x0101NFADFA0q1q2001

像这里, 在q2可以去往1, 也可以去往3, 所以就创建一个节点同时代表q1和q3, 它包含了q1和q3可能去的地方, 如果q3还可以再回到q1, 则还需要创建一个节点, 说明状态可能同时再q1和q2
现在需要解决带有ε转移方程的NFA了:
其实这个在理解上面的方法以后也比较好解决了:
比如从q2可以通过ε转移到q3, 也就是说q2可以直接到q3不需要任何字符. 那么就直接加一个节点叫q2,q3, 如果从q1转移到q2的时候就直接转移到这个节点就行, 也就表示它既可以到q2, 也可以到q3
q1q2q30,ε11q1q2q1q2q31x0NFADFAq20101

Regular Expression

在数学中, 我们用运算符来表达出算式, 同样的, 我们可以用正则表达式来表示一个语言:
如果R是其中一下之一, 那么这个R就是regular expression:
Pasted image 20250115143937.png
运算符也是有先后顺序的:

简写

对于1, a是对于{a}的简写, 也就是一个只包含a字符的语言.
对于, 这个也有简写: 可以把它省略掉, 直接写R1R2, 就表示两个语言的连接

例子:

Regex == Reg language

理论: 如果一个语言是regular的, 则一定有一个正则表达式可以表达它

Lamma1:
如果存在一个正则表达式, 则我们可以把它画成一个NFA (可以表明它是regular的)

想证明这个是可以做到的: 可以把上面的Regular expression的组成的6个基础部分都化成NFA, 那么不管正则表达式有多复杂, 总有NFA可以表达出来.

6个组成部分分为两个部分:

  • R is atomic: 语言构成非常简单, 要不就是一个字符, 或者空集
  • R is composite: 这个语言是由两个其他的正则表达式通过合集, 连接, star组合而成

Atomic很简单, NFA可以轻易画出来, Composite也很简单 - 可以用closure constructions来证明

Lamma2:
如果存在一个正则语言, 则一定存在一个正则表达式表达出来它.

这个证明比较复杂, 我们需要一个GNFA来证明. 这个跟NFA不同的是, 它的每条路线(状态转移方程)是可以由正则表达式来表达的.

然后, 还需要多个个Special form假设:

  • 存在一个GNFA, 它跟上面设计的GNFA是一样的, 但它只有一个accept state, 且不在起始点. 这个可以做到, 只要把所有的accept state用一个接受空字符的转移方程连到一个新的accept state就行了.
  • 任何其他state不能转移到start state. 所以我们可以创建一个新的start state, 然后用空字符串的转移方程连接到原本的start state
  • accept state 只能被其他state指向, 不能指向任何其他的state

通过上面的三条操作, 就可以把一个GNFA来转化成一个special form的GNFA. 然后我们的目标就是把它变成一个正则表达式.

这可以用数学归纳法来归纳含有k个state的GNFA图G.
Basis: k = 2
这时候, 只有两个state, 起始点不是accept state, 然后用一个Regex (r)连接一个accept state. 答案很明显, 我们想找的正则表达式R就是状态转移方程r

Incudtion step: k > 2
我们会假设k-1个state都是可以转化成正则表达式的(数学归纳法原理), 然后需要证明有k个state也可以转换成Regex.
对于一个k state的Machine, 我们可以去掉一个非起始非结束的state, 变成一个k-1 state的 Machine. 但由于我们删掉一个点, 这个Machine就已经不等同于之前的Machine了, 所以我们需要把这个新Machine进行修改, 这样它又变成了以前的Machine, 唯一的区别就是少了一个state.
我们可以这么修复: 假设从o->p->q, 他们的转移方程分别是r1r2, 我们删掉了p state. 我们可以直接把o state 连接q state, 然后用一个正则表达式r1r2(两个表达式连接起来)连接oq. 这样, 就可以保证这个machine 和原来的machine认识的语言是一样的. 如果被删掉的p state还会指向自己, 则可以在r1r2表达式中间加上个r*, 表示中间夹多少个这个转移方程都没关系.
通过重复这样的操作, 我们需要把所有指向p state的state都用正则表达式连接到新的state.

Induction Conclusion: 因为Base case和 Induction Step都证明过, 所以这个假设成立

GNFA -> Regex:
上面已经证明了一个GNFA可以转化成表达式, 那么来实际操作一下:
实际操作就是一直在重复Induction Step里的东西: 一直去删除图中的某个State, 然后把删掉一个State的GNFA修改成跟原来相同的GNFA. 重复到只有start state 和Accept state.

总结

现在, 对于一个语言A, 我们可以用NFA, DFA或者Regex来判断它到底不是regular
但我们仍然无法设计出任何机器来识别下面的语言:
这就涉及到 None Regular Language了.

None Regular Language

如果一个语言没有NFA或DFA去识别A语言, 则这个A语言就是None Regular Language. 通常, 这个是比寻找一个能识别某个语言的DFA要困难的, 因为我们需要去证明这个语言为什么不能被NFA / DFA识别.
比如这个语言, 因为NFA / DFA没有记忆去记住能有多少个0和1出现, 所以就没办法识别

Pumping Lamma:

这个假设说的是对于每一个regular language, 一定有一个数字p(pumping length)
如果一个字符串属于这个语言中, 并且字符串的长度≥p, 则这个字符串合约被分成三个部分xyz. 这个xyz三个部分需要满足下面三个条件
比如一个regular 语言A={x, y, z, w}, 这四个string的长度均没超过100, 那么我们直接说p=101, 那么这个语言直接满足Pumping Lamma
从此可以看出来, 如果想要使用这个Pumping Lamma, 就需要这个语言的字符长度至少是无限的.

Proof:

使一个DFA M 认识A语言, 然后把它的state number记作p, 然后我们选择一个长度≥p的字符串. 这个长度的字符串会让某个节点一定访问两次或以上

所以, 可以简化成这样一个表格:
qjyzx

这个访问两次或以上的节点记作qj, 然后把它自循环当作上面的y. 它可以无限次循环, 都满足第一个规则
第三个规则可以这么满足: 我们把第一个循环的出现当作qj, 这样, x没有任何循环, y就算有循环, 一边走完剩下的节点也不会超过p, 所以|xy|的长度就一定是小于等于p的, 后面的部分算在z头上.

实践:
接下来就来看怎么证明这个语言不是regular的, 通过proof by contradiction
也就是说, 我们需要证明不管哪个p, 都会找出不满足规则的某个字符串.

首先假设它是正则的, 所以会存在一个p这样, 这个字符串s一定可以被分为三个部分xyz, 由于规则规定一定要有y, 所以我们把00001111中的一段0当作y.
虽然前两个规则可以满足, 但只要我们根据规则, 来增加y的数量, 那么这个新的字符串就不会满足规则, 因为0000 0 1111就有不相等数量的0,1了. 中间隔开的0就是第二个y
这样, 不管什么p, 都满足不了上面的要求

实践2:
上面的表示有两段字符串, 字符内容怎么排列, 怎么重复都可以. 但这两段字符串需要相等
这种情况, 我们连怎么分割都不知道.

仍然是Proof By Contradiction
可能第一想到的是用上面的测试: 然而实际上是不行的, 因为如果把y当作两个0, 就可以让字符串永远是双数.

其实, 我们可以写成这样:原理跟上面差不多其实, 这个s字符串是000...01 000...01 这样, 如果我们把y看作0, 也就是第一个重复的地方, 那么如果我们把y重复, 则后半段的字符串就不会跟前面的相等.

实践3:
我们可以说这个pumping lamma是:
由于规则2, 3, y必须是一个或多个0, 但这样的话, 如果根据规则1, 把y删掉, 则这个s则不再满足有0比1多的特点了. 因为y一定含有个0, 所以(p+1)-1=p

实践4 - 用闭包性质来证明:
首先, 我们可以构建出0*1*的NFA, 就是两个节点能做到的事
根据闭包性质, 两个Regular Language做操作还会得到一个Regular Language, 也就是说A=D∩0*1*会得到一个regular的语言A, 但得到的结果是
而这个A已经被证明过不是regular的

实践5:
然后, 我们可以用下面的这个方式来永远找到一个xyz来符合pumping lamma:
Pasted image 20250127144651.png

注意

但需要注意的是, 虽然不满足pumping lamma的永远不是regular language, 但满足这个的, 不一定是regular language